1616. Prime number?

Check if the given number is prime. The number is prime if it has no more than two divisors: 1 and the number itself.

Input. One positive signed 32-bit integer n.

Output. Print “Yes” if the number is prime, and “No” otherwise.

Sample input	Sample output
5	Yes

SOLUTION

prime test

Algorithm analysis

The number is called prime if its only factors are 1 and itself.

Тheorem. If number n is composite, then it has a divisor no more than .

Proof. Let n be composite and d its divisor. Then n / d is also a divisor of n. Assuming that all divisors of n are greater than , then d > and n / d > . Hence we have d * (n / d) > * or n > n. Contradiction.

To test the number n for primality, it is enough to check whether it is divisible by one of the numbers from 2 to inclusive. If n is divisible by at least one of them, then n is composite. Otherwise it is prime.

Algorithm realization

Read the value of n. Set initially flag = 1.

scanf("%d",&n);

flag = 1;

Run through all possible divisors i of number n. If n is divisible by i, it is composite, set flag = 0.

for(i = 2; i <= sqrt(n); i++)

if (n % i == 0)

{

flag = 0;

break;

}

Depending on the value of flag print the answer.

if (flag == 0) printf("No\n"); else printf("Yes\n");

Algorithm realization – function for primality testing

#include <stdio.h>

#include <math.h>

int n;

int IsPrime(int n)

{

for(int i = 2; i <= sqrt(n); i++)

if (n % i == 0) return 0;

return 1;

}

int main(void)

{

scanf("%d",&n);

if (IsPrime(n)) printf("Yes\n"); else printf("No\n");

return 0;

}

Java realization

import java.util.*;

public class Main

{

static boolean IsPrime(int n)

{

for(int i = 2; i <= Math.sqrt(n); i++)

if (n % i == 0) return false;

return true;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

if (IsPrime(n))

System.out.println("Yes");

else

System.out.println("No");

con.close();

}

}

Python realization

import math

def IsPrime(n):

for i in range(2, int(math.sqrt(n))+1):

if n % i == 0: return False

return True

n = int(input())

if IsPrime(n):

print("Yes")

else:

print("No")